Search results for "Turing completeness"

showing 2 items of 2 documents

Ultrametric Finite Automata and Turing Machines

2013

We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceComputer scienceSuper-recursive algorithmProbabilistic Turing machineDescription numberNonlinear Sciences::Cellular Automata and Lattice GasesTuring machinesymbols.namesakeTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESTuring completenesssymbolsQuantum finite automataAutomata theoryTwo-way deterministic finite automatonComputer Science::Formal Languages and Automata TheoryMathematicsofComputing_DISCRETEMATHEMATICS
researchProduct

Quantum Real - Time Turing Machine

2001

The principles of quantum computation differ from the principles of classical computation very much. Quantum analogues to the basic constructions of the classical computation theory, such as Turing machine or finite 1-way and 2-ways automata, do not generalize deterministic ones. Their capabilities are incomparable. The aim of this paper is to introduce a quantum counterpart for real - time Turing machine. The recognition of a special kind of language, that can't be recognized by a deterministic real - time Turing machine, is shown.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceQuantum Turing machineDTIMEComputer scienceProbabilistic Turing machine2-EXPTIMESuper-recursive algorithmComputationDescription numberDSPACElaw.inventionsymbols.namesakeTuring machineTuring completenessNon-deterministic Turing machinelawAlgorithm characterizationsQuantumPSPACEQuantum computerFinite-state machineTuring machine examplesNSPACETheoryofComputation_GENERALAutomatonTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESTuring reductionTheory of computationsymbolsUniversal Turing machineTime hierarchy theoremAlternating Turing machineComputer Science::Formal Languages and Automata TheoryRegister machine
researchProduct